package practice_2025_9.practice_9_24;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class Solution {
    /**
     * 移除 k 位数字
     * @param num
     * @param k
     * @return
     */
    public String removeKdigits(String num, int k) {
        // 移除这个数中的 k 位数字, 使得剩下的数字最小
        // 剩下数字最小 -> 删除数字尽量在高位
        // 使用栈删除高位较大数字 
        // 若当前位小于前一位 -> 前一位出栈
        // 遍历完成 -> 栈中元素顺序排列
        // 依次删除最大元素
        int len = num.length();
        if (len <= 0 || len <= k) {
            return "0";
        }
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for(int i = 0; i < num.length(); i++) {
            char ch = num.charAt(i);
            while (!stack.isEmpty() && ch < stack.peek() && count < k) {
                stack.pop();
                count++;
            }
            // 栈为空 & 当前元素为0 -> 前导0
            if (!(stack.isEmpty() && ch == '0')) {
                stack.add(ch);
            }
        }
        // 此时栈中元素顺序排序
        while (!stack.isEmpty() && count < k) {
            stack.pop();
            count++;
        }
        if (stack.isEmpty()) {
            return "0";
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }

    /**
     * 恢复二叉搜索树
     */
    // 二叉搜索树 中序遍历具有 顺序性
    // 找到不符合顺序的两个节点
    List<TreeNode> list = new ArrayList<>();
    public void recoverTree(TreeNode root) {
        // 先将所有节点按 中序遍历 顺序放入列表中
        dfs(root);
        // 在列表中找到不符合 升序 的两个节点
        TreeNode node1 = null, node2 = null;;
        int i = 0;
        for(; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i + 1).val) {
                node1 = list.get(i);
                node2 = list.get(i + 1);
                break;
            }
        }
        i++;
        // 判断后续是否是升序
        for(;i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i +1).val) {
                node2 = list.get(i + 1);
                break;
            }
        }
        // System.out.println("node1: " + node1.val + " node2: " + node2.val);
        // 交换两节点的值
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
    // 中序遍历
    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left);
        }
        list.add(root);
        if (root.right != null) {
            dfs(root.right);
        }
    }

    // 二叉搜索树 中序遍历具有 顺序性
    // 找到不符合顺序的两个节点
    // 增加一个辅助节点, 记录上一个节点的值
    TreeNode node1, node2, prev;

    /**
     * 恢复二叉搜索树 - 不使用额外空间
     * @param root
     */
    public void recoverTree2(TreeNode root) {
        // 先将所有节点按 中序遍历 顺序放入列表中
        dfs2(root);
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
    // 中序遍历
    public void dfs2(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            dfs(root.left);
        }
        if (prev != null && prev.val > root.val) {
            node2 = root;
            if (node1 == null) {
                node1 = prev;
            }
        }
        prev = root;
        // list.add(root);
        if (root.right != null) {
            dfs(root.right);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.removeKdigits("33526221184202197273", 19);
    }
}